package com.work.daily;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by suk on 2020/8/25.
 */
public class D3_FindSubsequences_491_1 {

    public static void main(String[] args) {
        D3_FindSubsequences_491_1 d3 = new D3_FindSubsequences_491_1();
        int[] nums = {4,6,7,8};
        System.out.println(d3.findSubsequences(nums));
    }

    /**
     * 我不懂~
     */
    List<Integer> temp = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        // 启动
        dfs(0, Integer.MIN_VALUE, nums);
        return ans;
    }

    public void dfs(int cur, int last, int[] nums) {
        // 终结条件
        if (cur == nums.length) {
            if (temp.size() >= 2) {
                ans.add(new ArrayList<>(temp));
            }
            return ;
        }
        // 当前元素大于等于上一个被选择的元素时才被加入
        if (nums[cur] >= last) {
            temp.add(nums[cur]);
            //
            dfs(cur + 1, nums[cur], nums);
            // 回溯必须清理掉末尾结点
            temp.remove(temp.size() - 1);
        }
        // 过滤掉两个数相等的情况
        if (nums[cur] != last) {
            dfs(cur + 1, last, nums);
        }
    }
}
